#include "MyString.h"
#include <cstring>
#include <cstdlib>
#include "Exception.h"
#include "LinkQueue.h"

namespace MySTL
{

void String::init(const char* str)
{
	m_length = 0;

	m_str = strdup(str ? str : "");
	if (NULL == m_str)
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to construct String...");
	}

	m_length = (int)strlen(m_str);
}

String::String()
{
	init(NULL);
}

String::String(const char* str)
{
	init(str);
}

String::String(char c)
{
	char str[] = { c, '\0' };
	init(str);
}

String::String(const String& obj)
{
	init(obj.m_str);
}

String::~String()
{
	free(m_str);
}

void String::update(const char* str)
{
	m_length = 0;
	free(m_str);
	m_str = NULL;

	init(str);
}

String& String::operator =(const char* str)
{
	update(str);

	return *this;
}

String& String::operator =(char c)
{
	char str[] = { c, '\0' };
	update(str);

	return *this;
}

String& String::operator =(const String& obj)
{
	if (this != &obj)
	{
		update(obj.m_str);
	}

	return *this;
}

char& String::operator [](int n)
{
	if (n >= 0 && n < m_length)
	{
		return m_str[n];
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index out of bounds in char& String::operator [](int pos)");
	}
}

const char& String::operator [](int n) const
{
	return const_cast<String&>(*this)[n];
}

bool String::equal(const char* str, int from, int to) const
{
	bool ret = true;

	for (int i = from, j = 0; i <= to; ++i, ++j)
	{
		if (m_str[i] != str[j])
		{
			ret = false;
			break;
		}
	}

	return ret;
}

bool String::startWith(const char* str) const
{
	int len = (int)strlen(str ? str : "");

	if (len <= 0 || len > m_length)
	{
		return false;
	}
	else
	{
		return equal(str, 0, len - 1);
	}
}

bool String::startWith(const String& obj) const
{
	return startWith(obj.m_str);
}

bool String::endOf(const char* str) const
{
	int len = (int)strlen(str ? str : "");

	if (len <= 0 || len > m_length)
	{
		return false;
	}
	else
	{
		return equal(str, m_length - len, m_length - 1);
	}
}

bool String::endOf(const String& obj) const
{
	return endOf(obj.m_str);
}

int String::length() const
{
	return m_length;
}

const char* String::c_str() const
{
	return m_str;
}

String& String::trim()
{
	if (m_length <= 0)
		return *this;

	int start = 0, end = m_length - 1;

	while (start < end && m_str[start] == ' ')
		++start;

	while (end >= start && m_str[end] == ' ')
		--end;

	if (end < start)
	{
		update("");
	}
	else
	{
		int len = end - start + 1;

		char* str = (char*)malloc(len + 1);
		if (NULL != str)
		{
			strncpy(str, m_str + start, len);
			str[len] = '\0';
			free(m_str);
			m_str = str;
			m_length = len;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to trim String...");
		}
	}

	return *this;
}

String& String::insert(int n, const char* str)
{
	int len = (int)strlen(str ? str : "");

	if (n >= 0 && n <= m_length && len > 0)
	{
		char* s = static_cast<char*>(malloc(m_length + len + 1));
		if (NULL != s)
		{
			strncpy(s, m_str, n);
			strncpy(s + n, str, len);
			strncpy(s + n + len, m_str + n, m_length - n);
			s[m_length + len] = '\0';

			free(m_str);
			m_length = m_length + len;
			m_str = s;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to insert String in String& String::insert(int pos, const char* str)");
		}
	}
	else
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in String& String::insert(int pos, const char* str)");
	}

	return *this;
}

String& String::insert(int n, const String& obj)
{
	return insert(n, obj.m_str);
}

String& String::remove(int n, int len)
{
	if (n < 0 || n >= m_length || len <= 0)
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in String& String::remove(int pos, int len)");
	}

	if (n + len - 1 >= m_length)
	{
		len = m_length - n;
	}

	char* s = static_cast<char*>(malloc(m_length - len + 1));
	
	if (NULL != s)
	{
		strncpy(s, m_str, n);
		strncpy(s + n, m_str + n + len, m_length - n - len);
		s[m_length - len] = '\0';

		free(m_str);
		m_length = m_length - len;
		m_str = s;
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to remove String in String& String::remove(int pos, int len)");
	}

	return *this;
}

String& String::remove(const char* str)
{
	int len = (int)strlen(str ? str : "");

	if (len > 0)
	{
		int count = 0;
		int index = indexOf(str);
		int pos = index;
		int last_index = index;

		if (index >= 0)
		{
			while (((index = indexOf(str, last_index + len)) > last_index) || (index = m_length))
			{
				for (int i = 0; i < index - (last_index + len); ++i, ++pos)
				{
					m_str[pos] = m_str[last_index + len + i];
				}
				++count;
				if (index == m_length)
					break;
				last_index = index;
			}

			m_str[m_length - count * len] = '\0';

			char* s = static_cast<char*>(malloc(m_length - count * len + 1));
			if (NULL != s)
			{
				strcpy(s, m_str);

				free(m_str);
				m_str = s;
				m_length = m_length - count * len;
			}
			else
			{
				THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to remove String in String& String::remove(const char* str)");
			}
		}
	}

	return *this;
}

String& String::remove(const String& obj)
{
	return remove(obj.m_str);
}

String& String::replace(int n, int len, const char* str)
{
	if (n < 0 || n >= m_length || len <= 0 || NULL == str)
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in String& String::replace(int n, int len)");
	}

	if (n + len > m_length)
	{
		len = m_length - n;
	}

	int str_len = (int)strlen(str);

	if (len != str_len)
	{
		int new_len = m_length - len + str_len;
		char* s = static_cast<char*>(malloc(new_len + 1));
		if (NULL != s)
		{
			strncpy(s, m_str, n);
			strncpy(s + n, str, str_len);
			strncpy(s + n + str_len, m_str + n + len, m_length - len - n);
			s[new_len] = '\0';

			free(m_str);
			m_str = s;
			m_length = new_len;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to replace String in String& String::replace(int n, int len, const char* str)");
		}
	}
	else
	{
		strncpy(m_str + n, str, len);
	}

	return *this;
}

String& String::replace(int n, int len, const String& str)
{
	return replace(n, len, str.m_str);
}

String& String::replace(const char* before, const char* after)
{
	if (NULL == before || NULL == after)
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in String& String::replace(const char* before, const char* after)");
	}

	int before_len = (int)strlen(before);
	int after_len = (int)strlen(after);

	if (before_len != after_len)
	{
		LinkQueue<int> queue;
		int index = indexOf(before, 0);

		while (index >= 0)
		{
			queue.enqueue(index);
			index = indexOf(before, index + before_len);
		}

		if (queue.length() > 0)
		{
			int new_len = m_length + queue.length() * (after_len - before_len);
			char* s = static_cast<char*>(malloc(new_len + 1));
			if (NULL != s)
			{
				int i1 = 0;
				int i2 = 0;
				int cursor = 0;
				while (queue.length() > 0)
				{
					i2 = queue.dequeue();

					strncpy(s + cursor, m_str + i1, i2 - i1);
					cursor += i2 - i1;
					strncpy(s + cursor, after, after_len);
					cursor += after_len;

					i1 = i2 + before_len;
				}
				strncpy(s + cursor, m_str + i1, m_length - i1);
				s[new_len] = '\0';

				free(m_str);
				m_str = s;
				m_length = new_len;
			}
			else
			{
				THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to replace String in String& String::replace(const char* before, const char* after)");
			}
		}
	}
	else
	{
		int index = indexOf(before, 0);

		while (index >= 0)
		{
			strncpy(m_str + index, after, after_len);
			index = indexOf(before, index + before_len);
		}
	}

	return *this;
}

String& String::replace(const String& before, const char* after)
{
	return replace(before.m_str, after);
}

String& String::replace(const char* before, const String& after)
{
	return replace(before, after.m_str);
}

String& String::replace(const String& before, const String& after)
{
	return replace(before.m_str, after.m_str);
}

int String::indexOf(const char* str, int from) const
{
	return kmp(str, from);
}

int String::indexOf(const String& str, int from) const
{
	return kmp(str.m_str, from);
}

bool String::operator ==(const char* str) const
{
	return strcmp(m_str, str ? str : "") == 0;
}

bool String::operator ==(const String& obj) const
{
	return *this == obj.m_str;
}

bool String::operator !=(const char* str) const
{
	return strcmp(m_str, str ? str : "") != 0;
}

bool String::operator !=(const String& obj) const
{
	return *this != obj.m_str;
}

bool String::operator <(const char* str) const
{
	return strcmp(m_str, str ? str : "") < 0;
}

bool String::operator <(const String& obj) const
{
	return *this < obj.m_str;
}

bool String::operator <=(const char* str) const
{
	return strcmp(m_str, str ? str : "") <= 0;
}

bool String::operator <=(const String& obj) const
{
	return *this <= obj.m_str;
}

bool String::operator >(const char* str) const
{
	return strcmp(m_str, str ? str : "") > 0;
}

bool String::operator >(const String& obj) const
{
	return *this > obj.m_str;
}

bool String::operator >=(const char* str) const
{
	return strcmp(m_str, str ? str : "") >= 0;
}

bool String::operator >=(const String& obj) const
{
	return *this >= obj.m_str;
}

int* String::get_pmt(const char* str, int len) const
{
	if (NULL == str || len <= 0)
	{
		return NULL;
	}

	int* ret = static_cast<int*>(malloc(len * sizeof(int)));

	if (ret)
	{
		ret[0] = 0;
		int ll = 0;

		for (int i = 1; i < len; ++i)
		{
			while (ll > 0 && str[i] != str[ll])
			{
				ll = ret[ll - 1];
			}

			if (str[i] == str[ll])
			{
				++ll;
			}

			ret[i] = ll;
		}
	}

	return ret;
}

int String::kmp(const char* str, int from) const
{
	int ret = -1;

	if (NULL == str || from < 0 || from >= m_length)
	{
		return ret;
	}

	int len = (int)strlen(str);
	if (len <= 0 || (len > m_length - from))
	{
		return ret;
	}
	
	int* pmt = get_pmt(str, len);
	if (NULL != pmt)
	{
		for (int i = from, j = 0; i < m_length; ++i)
		{
			while (j > 0 && m_str[i] != str[j])
			{
				j = pmt[j - 1];
			}

			if (m_str[i] == str[j])
			{
				++j;
			}

			if (j == len)
			{
				ret = i - len + 1;
				break;
			}
		}
	}

	free(pmt);

	return ret;
}

}